package heap;

import java.util.*;

/**
 * @author pengfei.hpf
 * @date 2020/2/28
 * @verdion 1.0.0
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 *
 * 示例 1:
 *
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 *
 * 输入: nums = [1], k = 1
 * 输出: [1]
 * 说明：
 *
 * 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 * 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/top-k-frequent-elements
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class TopKFrequent {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();

        if(nums == null || nums.length == 0){
            return res;
        }
        PriorityQueue<Count> queue = new PriorityQueue<>(k, (c1,c2)-> c2.count - c1.count);
        Map<Integer, Count> map = new HashMap<>();
        for(int i = 0; i < nums.length; i ++){
            Count count;
            if(map.containsKey(nums[i])){
                count = map.get(nums[i]);
            } else {
                count = new Count(nums[i]);
            }
            count.count ++;
            map.put(nums[i], count);
        }
        for(Map.Entry<Integer, Count> entry: map.entrySet()){
            queue.add(entry.getValue());
        }
        for(int i = 0; i < k; i ++){
            if(!queue.isEmpty()) {
                res.add(queue.poll().val);
            }
        }
        return res;
    }

    class Count{
        int val;
        int count;
        Count(int v){
            val = v;
            count = 1;
        }
    }
}
